package a09_贪心算法;

/**
 * <p>
 * a08_跳跃游戏2复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/2/17
 */
public class a08_跳跃游戏2复习2 {
    public static void main(String[] args) {
        System.out.println(jump(new int[]{2, 3, 1, 1, 4}));
    }


    //当前这一步有很多种情况，统计走的每一种情况下一步的最大覆盖范围
    //每次统计完下一步的最大覆盖范围时，判断下一个最大覆盖范围是否能到终点
    //如果统计到最后一种情况还不行，那么就走一步，更新当前遍历和下一个覆盖范围

    //2, 3, 1, 1, 4
    //模拟：
    //刚开始currentCover=0
    //到达索引0的时候：cover = 2
    //到达索引0的时候：cover = 2
    public static int jump(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        int currentCover = 0;
        int nextCover = 0;
        int minStep = 0;
        for (int i = 0; i <= currentCover; i++) {
            nextCover = Math.max(nextCover, i + nums[i]);
            if(nextCover >= nums.length - 1){//先判断下一个步覆盖范围是否到达终点了
                return minStep + 1;
            }
            if(i == currentCover){//已经到了最后一个了 更新当前的范围 更新下一个的范围
                currentCover = nextCover;
                nextCover = 0;
                minStep++;
            }
        }
        return minStep;
    }
}
